package leetcode.每日一题;

import org.junit.Test;

import java.util.Arrays;
import java.util.HashSet;
import java.util.PriorityQueue;

/**
 * @author :songyaozhang
 * @date :Created 2021/8/9 9:57
 * @description :https://leetcode-cn.com/problems/super-ugly-number/
 */
public class 超级丑数 {
    @Test
    public void test() {
        Solution solution = new Solution();
        System.out.println(solution.nthSuperUglyNumber(12, new int[]{2, 7, 13, 19}));
    }

    /*
    //动态规划
    class Solution {
        public int nthSuperUglyNumber(int n, int[] primes) {
            int[] dp = new int[n + 1];
            dp[1] = 1;
            int[] dpIdx = new int[primes.length];
            Arrays.fill(dpIdx, 1);
            for (int i = 2; i <= n; i++) {
                int min = Integer.MAX_VALUE;
                for (int j = 0; j < primes.length; j++) {
                    min = Math.min(min, dp[dpIdx[j]] * primes[j]);
                }
                dp[i] = min;
                for (int j = 0; j < primes.length; j++) {
                    if (min == dp[dpIdx[j]] * primes[j]) {
                        dpIdx[j]++;
                    }
                }
            }
            return dp[n];
        }
    }
     */

    class Solution {
        public int nthSuperUglyNumber(int n, int[] primes) {
            PriorityQueue<Long> queue = new PriorityQueue<>();
            HashSet<Long> set = new HashSet<>();
            queue.offer(1L);
            long cur = 1;
            for (int i = 1; i <= n; i++) {
                cur = queue.poll();
                for (int prime : primes) {
                    if (set.add(cur * prime))
                        queue.offer(cur * prime);
                }
            }
            return (int) cur;
        }
    }


}
